use std::iter::once;

pub trait ModComputation {
    /// Calculates `self * other % modulus` without overflow.
    fn mul_mod(self, other: Self, modulus: Self) -> Self;
    /// Calculates `self ^ exp % modulus` efficiently, using the "square and multiply" method.
    fn pow_mod(self, exp: Self, modulus: Self) -> Self;
}

impl ModComputation for u64 {
    fn mul_mod(mut self, mut other: Self, modulus: Self) -> Self {
        // For small `modulus` or small `self * other`, we can use the naive method.
        self %= modulus;
        other %= modulus;
        if let Some(product) = self.checked_mul(other) {
            return product % modulus;
        }
        (self as u128 * other as u128 % modulus as u128) as Self
    }

    fn pow_mod(mut self, mut exp: Self, modulus: Self) -> Self {
        if self == 1 || exp == 0 {
            return 1;
        }
        let mut acc = 1;

        loop {
            if (exp & 1) == 1 {
                acc = acc.mul_mod(self, modulus);
                if exp == 1 {
                    return acc;
                }
            }
            exp >>= 1;
            self = self.mul_mod(self, modulus);
        }
    }
}

const SMALL_ODD_PRIMES: &[u64] = &[
    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
];

fn is_odd_prime(n: u64) -> bool {
    debug_assert_eq!(n & 1, 1);

    for &p in SMALL_ODD_PRIMES {
        if n == p {
            return true;
        } else if n % p == 0 {
            return false;
        }
    }

    is_prime_mr(n)
}

/// A wrapper function for `miller_rabin`, to test whether a number is prime.
///
/// `n` should be checked against small primes
fn is_prime_mr(n: u64) -> bool {
    // Miller-Rabin bases selected from <https://miller-rabin.appspot.com/>.
    // over 2^18
    if n < 341531 {
        miller_rabin(n, once(9345883071009581737))
    }
    // over 2^29
    else if n < 1050535501 {
        miller_rabin(n, [336781006125, 9639812373923155])
    }
    // over 2^38
    else if n < 350269456337 {
        miller_rabin(
            n,
            [
                4230279247111683200,
                14694767155120705706,
                16641139526367750375,
            ],
        )
    }
    // over 2^38
    else if n < 55245642489451 {
        miller_rabin(
            n,
            [
                2,
                141889084524735,
                1199124725622454117,
                11096072698276303650,
            ],
        )
    }
    // over 2^52
    else if n < 7999252175582851 {
        miller_rabin(
            n,
            [
                2,
                4130806001517,
                149795463772692060,
                186635894390467037,
                3967304179347715805,
            ],
        )
    }
    // over 2^52
    else if n < 585226005592931977 {
        miller_rabin(
            n,
            [
                2,
                123635709730000,
                9233062284813009,
                43835965440333360,
                761179012939631437,
                1263739024124850375,
            ],
        )
    } else {
        miller_rabin(n, [2, 325, 9375, 28178, 450775, 9780504, 1795265022])
    }
}

/// Performs the Miller-Rabin primality test on `n` using the given `bases`.
///
/// If `n` is composite for any `base`, then `false` is returned.
/// Else `true` is returned, indicating that `n` is probably prime.
fn miller_rabin<I>(n: u64, bases: I) -> bool
where
    I: IntoIterator<Item = u64>,
{
    for base in bases {
        // Miller-Rabin test is based on the following theorem:
        //     If n is an odd prime,
        //     let n - 1 = d * 2^s, where d is odd.
        //     Then ∀a coprime to n,
        //         a^d ≡ 1 (mod n)                        (1), or
        //         ∃r ∈ [0, s), a^(2^r * d) ≡ -1 (mod n)  (2)
        let mut d = n - 1;
        let s = d.trailing_zeros();
        d >>= s;

        let mut x = base.pow_mod(d, n);

        if x == 1 {
            continue;
        }

        for r in 0..s {
            if x == n - 1 {
                break;
            } else if r == s - 1 {
                // We failed to find an `r` as described in (2).
                return false;
            }

            x = x.mul_mod(x, n);

            if x == 1 {
                // A non-trivial square root of 1 modulo `n` is found.
                // If `n` is prime, the only possible solutions of x^2 ≡ 1 (mod n)
                // are x ≡ 1 (mod n) and x ≡ 1 (mod n).
                // `n` must be composite.
                return false;
            }
        }
    }
    // All tests has passed, `n` is a probably prime, given the bases.
    true
}

fn primes_in_layer(layers: u64) -> u32 {
    let length = 2 * layers + 1;
    // bottom_right must be composite
    let bottom_right = length * length;
    let bottom_left = bottom_right - length + 1;
    let top_left = bottom_left - length + 1;
    let top_right = top_left - length + 1;

    // all the corners are odd

    [bottom_left, top_left, top_right]
        .into_iter()
        .filter(|&n| is_odd_prime(n))
        .count() as u32
}

pub fn min_edge_prime_num(number: u32) -> String {
    let mut primes = 0;
    let mut total = 1;

    for layer in 1.. {
        total += 4;
        primes += primes_in_layer(layer);

        if primes * 100 / total < number {
            return format!("{},{}", layer * 2 + 1, primes);
        }
    }

    unreachable!()
}
